package lq3521;

import java.util.Deque;
import java.util.LinkedList;

public class Main {

	static int[][] m = {
				{83	,96	,90	,4	,68	,54},
				{66	,79	,46	,26	,1	,21},
				{86	,53	,88	,82	,76	,89},
				{1	,64	,71	,52	,93	,7},
				{96	,75	,73	,73	,92	,86},
				{58	,83	,10	,73	,7	,64}
			};
	static int[][] hangmax = new int[6][6];
	static int[][] liemax = new int[6][6];
	
	//计算3X3区间的最值
	public static void main(String[] args) {
		
		//按行计算最值
		//遍历行
		for(int h=0;h<6;h++) {
			//每行计算长为3的最值
			int k = 3;
			//实例化双向队列
	        Deque<Integer> queue = new LinkedList<>();
	        //遍历原始数组
	        for(int i = 0; i < 6; i++){
	        	//单调队列入队操作第一步：删除队尾小于等于待入队数值的项，注意队列保存的是下标不是具体元素
	            while(!queue.isEmpty() && m[h][queue.peekLast()] <= m[h][i]){
	                queue.removeLast();
	            }
	            //单调队列入队操作第一步：放入队尾，注意队列保存的是下标不是具体元素
	            queue.add(i);
	            //如果队头的下标在区间范围外了，移除队头元素
	            if(queue.peekFirst() <= i - k){
	                queue.removeFirst();
	            }
	            
	            //此时[i-k,i]区间内的最大值就是队列头的值，
	            //注意获取值后不要出队列
	            if(i >= k-1){
	            	hangmax[h][i] = m[h][queue.peekFirst()];
	            }
	        }
			
		}
		
		//输出hangmax
		System.out.println("按行计算最大值：");
		for(int i=0;i<6;i++) {
			for(int j=0;j<6;j++) {
				System.out.printf("%2d,", hangmax[i][j]);
			}
			System.out.println();
		}
		
		
		//按行计算最值
		//遍历列，从下标为行区间长度减1的位置开始
		for(int l=2;l<6;l++) {
			//每列计算长为3的最值
			int k = 3;
			//实例化双向队列
	        Deque<Integer> queue = new LinkedList<>();
	        //遍历hangmax数组
	        for(int i = 0; i < 6; i++){
	        	//单调队列入队操作第一步：删除队尾小于等于待入队数值的项，注意队列保存的是下标不是具体元素
	            while(!queue.isEmpty() && hangmax[queue.peekLast()][l] <= hangmax[i][l]){
	                queue.removeLast();
	            }
	            //单调队列入队操作第一步：放入队尾，注意队列保存的是下标不是具体元素
	            queue.add(i);
	            //如果队头的下标在区间范围外了，移除队头元素
	            if(queue.peekFirst() <= i - k){
	                queue.removeFirst();
	            }
	            
	            //此时[i-k,i]区间内的最大值就是队列头的值，
	            //注意获取值后不要出队列
	            if(i >= k-1){
	            	liemax[i][l] = hangmax[queue.peekFirst()][l];
	            }
	        }
			
		}
		
		//输出liemax
		System.out.println("对前面的结果矩阵，按列计算最大值，");
		System.out.println("即为每个3X3子矩阵的最大值：");
		for(int i=0;i<6;i++) {
			for(int j=0;j<6;j++) {
				System.out.printf("%2d,", liemax[i][j]);
			}
			System.out.println();
		}

	}

}
